\begin{enumerate}
\item[(a)] If a flow network $(V,E)$ has two minimum $s-t$ cuts $(S_1,T_1)$ and $(S_2,T_2)$ where $S_1,S_2 \subset V$ are the source sets (the set of vertices in the cut that contains the source) and $T_1,T_2 \subset V$ are the sink sets (the set of vertices in the cut that contains the sink), then show that $S_1 \cap S_2$ and $S_1 \cup S_2$ are also source sets for minimum cuts.
\item[(b)] Design an algorithm that finds a minimum $s-t$ cut $(S,T)$ in a flow network such that the size of the source set $|S|$ is minimum among all possible source sets in all minimum $s-t$
cuts in the network.
\item[(c)] Give a polynomial time algorithm to decide whether a flow network has a unique minimum
$s-t$ cut.
\end{enumerate}

\paragraph*{(a)} We will designate two cases:

\subparagraph*{If $S_1 \subseteq S_2$ or $S_2 \subseteq S_1$:} This case is trivial since the intersection ($S_1 \cap S_2$) equals with the smallest of the two sets, while the union ($S_1 \cup S_2$) equals with the larger one. Therefore, both the intersection and the union define a minimum cut.

\subparagraph*{If $S_1 \nsubseteq S_2$ and $S_2 \nsubseteq S_1$:} This means that there are some ``crossings'' between the two cuts in terms that on two different paths, the one cut contains an edge closer to $s$ on one while the other on the other path. 

\begin{wrapfigure}{l}{0.45\textwidth}
%  \vspace{-30pt}
  \begin{center}
    \input{cross.tex}
  \end{center}
%  \vspace{50pt}
\end{wrapfigure}

The graph on the left represents such an example. The two depicted graphs ``cross''. So the intersection of the two graphs contains only $s$.

Figure \ref{fig:cuts} generalizes the case. $S_1 \cap S_2$ and $S_1 \cup S_2$ define two cuts (name them $C_i$ and $C_u$ respectively). This is true since both $C_i$ and $C_u$ have $S$ sets that contain a directed graph of vetrices that are guaranteed to be disconnected from $t$, since their arcs will be saturated in the final residual graph.

The edges of $C_i$ combined with the ones from $C_u$ contain a subset of the edges of the combination of $C_1$ and $C_2$. This is due to the fact that none of the union or intersection contain the edges that ``cross'' (the ones in $S_2 - S_1$ and $S_1 - S_2$). $C_i$ clearly does not include them since it does not even contain the starting vertices in its $S$ set. $C_u$ does not include them because it includes both their starting and ending vertices in its $S$ set. This is due to the that the $S_2 - S_1$ vertices belong to the $S$ set for $C_2$ and the $T$ set for $C_1$, while the vertices in $S_1 - S_2$ belong to the $S$ set for $C_1$ and the $T$ set for $C_2$.

Therefore, $capacity(C_i) + capacity(C_u) \leq capacity(C_1) + capacity(C_2) = 2\times\text{MaxFlow}$. Assume, $capacity(C_i) + capacity(C_u) < 2\times\text{MaxFlow}$. Then one of the two cuts should have overall capacity less than the MaxFlow; a contradiction, since we now that a minimum cut on this graph has capacity exactly MaxFlow. Therefore, $capacity(C_i) + capacity(C_u) = 2\times\text{MaxFlow}$. With the exact same logic as before, non of the cuts may have capacity less than the MaxFlow, therefore $capacity(C_i) = capacity(C_u) = \text{MaxFlow}$. Consequently, $C_i$ and $C_u$ define two minimum cuts.
\vspace*{20pt}
\begin{figure}[h!]
  \begin{center}
    \input{cuts.tex}
  \end{center}
  \caption{The two cuts.}
  \label{fig:cuts}
\end{figure}

\paragraph*{(b)} Our algorithm takes the following steps:

\begin{itemize}
\item Calculate the maximum flow of the graph, thus resulting on the final residual graph.
\item On the final residual graph, use breadth first search (BFS) to find all the ``leaves'' for the graph which starts on $s$. These are the vertices that on the initial graph had connections with at least one vertex that now belongs to the $T$ set.
\end{itemize}

We first claim that constructed cut is minimum, as all edges in it are saturated by definition.. To be precise, the minimum cut consists of the saturated edges that start from one of the found vertices and end up on a vertex that was not found with the BFS. The collected vertices define the $S$ set with the wanted property, because the edges of every minimum cut are saturated on the final residual graph and we found a cut with a source set that has the first vertices in the path from $s$ from which only saturated edges are going further.
\\\\
An alternative approach for finding the minimum $S$ set would be to use the intersection property of question (a) to calculate the intersection of all $S$ sets ($\bigcap \limits _{\forall \text{min cut C}}S_C$), which by the definition of intersection will be the minimum $S$ set.

\subparagraph*{(c)} To find if a graph has a unique $s-t$ cut we first calculate the maximum flow (done in polynomial time) in order to get the final residual graph. 

On the residual graph we apply the algorithm of question (b) twice. This algorithm performs a BFS, thus takes polynomial time.

On the first run we apply it starting from $s$ in order to get the smaller minimum cut with the smaller $S$ set. On the second run we apply it starting from $t$ and use the inverse of the directed edges. By doing so we find the cut which has the minimum $T$ set, thus the larger $S$ set.

If the two minimum cuts found are the same, there is a unique minimum cut, else the algorithm will produce different cuts (the one with the smaller $S$ set and the one with the larger $S$ set). Since the comparison of the two sets take also polynomial time, all the steps of our algorithm can be performed in polynomial time, thus the overall complexity is polynomial.


